#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "uthash.h"

int numSquares(int n);

int main()
{
	return 0;
}

int numSquares(int n) {
	int* aux = (int*)calloc(sqrt(n) + 3, sizeof(int));
	for (int i = 1, len = sqrt(n) + 3; i < len; i++) aux[i] = i * i;
	int* dp = (int*)calloc(n + 1, sizeof(int));
	for (int i = 1; i <= n; i++) {
		dp[i] = i;
		for (int j = 1; i - aux[j] >= 0; j++) {
			dp[i] = fmin(dp[i], dp[i - aux[j]] + 1);
		}
	}
	return dp[n];
}
